package com.atcumt.Write.writeStructures;


import java.util.HashMap;
import java.util.Map;

class Node {

    int key,val;
    Node next,prev;
    public Node(int key,int val){
        this.key = key;
        this.val = val;
    }
}

/**
 * 双向链表
 * ● 首先是链表初始化，为了方便处理 i，虚拟一个头节点和尾结点。
 * ● 添加元素时，放到链表的尾部，表示该元素最近使用过
 * ● 删除双向链表的某个节点
 * ● 删除并返回头节点，表示删除最久未使用的元素
 * ● 返回链表当前长度
 */
class DoubleList {

    private Node head, tail; //虚拟出头节点和尾结点
    private int size;

    public DoubleList() {

        head = new Node(0, 0); //虚拟头结点
        tail = new Node(0, 0); //虚拟尾结点
        head.next = tail;
        tail.prev = head;
        size = 0;
    }

    // head <-> 1 <-> tail, 加入 x = 2, 放到链表的尾部
    public void addLast(Node x) {
        x.prev = tail.prev;
        x.next = tail; // head <-> 1 <- 2 -> tail

        tail.prev.next = x; // head <-> 1 <-> 2 -> tail
        tail.prev = x; // head <-> 1 <-> 2 <-> tail
        size++;
    }

    // head <-> 1 <-> 2 <-> tail, 删除 x = 2
    public void remove(Node x) {
        x.prev.next = x.next;
        x.next.prev = x.prev; // head <-> 1 <-> tail
        size--;
    }

    // 删除并返回头结点
    public Node removeHead () {
        if (head.next == tail) {
            return null;
        }
        Node first =  head.next;
        remove(first);
        return first; // 用于在哈希表中移除最久未使用的数据
    }

    public int getSize() {
        return size;
    }
}

public class LRUCache {

    private Map<Integer, Node> map;
    private DoubleList doubleList;
    private int cap;

    public LRUCache(int capacity) {
        this.map = new HashMap<>();
        this.doubleList = new DoubleList();
        this.cap = capacity;
    }

    // get 方法
    public int get(int key) {
        if (map.containsKey(key)) {
            makeRecently(key); // 先将key标记为最近使用，再返回value
            return map.get(key).val;
        } else {
            return -1;
        }
    }

    // 将key标记为最近使用的元素 (map中存在的)
    private void makeRecently(int key) {
        Node x = map.get(key);
        doubleList.remove(x);
        doubleList.addLast(x); // 尾部表示最近使用过的元素

    }

    // put 方法
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            deleteKey(key); // 从原 map 中移除该key
            addRecently(key, value); // 更新最近使用
            return;
        }

        int size = doubleList.getSize();
        if (size == cap) { // 说明需要移除最久未使用的元素了
            removeLeastRecently();
        }
        addRecently(key, value); // 添加新的元素进来
    }

    // 从原 map 和 cache 中移除该key
    private void deleteKey(int key) {
        Node x = map.get(key);
        map.remove(key);
        doubleList.remove(x);
    }

    // 添加最近使用过的元素，更新 map
    private void addRecently(int key, int value) {
        Node x = new Node(key, value);
        doubleList.addLast(x);
        map.put(key, x);
    }

    // 移除最久未使用的元素, 删除链表头部节点
    private void removeLeastRecently() {
        Node oldNode = doubleList.removeHead();
        int oldKey = oldNode.key;
        map.remove(oldKey);
    }

    // 测试
    public static void main(String[] args) {
        LRUCache lRUCache = new LRUCache(2);
        lRUCache.put(1, 1); // 缓存是 {1=1}
        lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
        System.out.println(lRUCache.get(1)); // 1
        lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
        System.out.println(lRUCache.get(2)); // -1 (未找到)
        lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
        System.out.println(lRUCache.get(1)); // -1 (未找到)
        System.out.println(lRUCache.get(3)); // 3
        System.out.println(lRUCache.get(4)); // 4
    }
}



